'''
Created on 2013-6-26

@author: ZuoPeng
'''
from fractions import gcd
import pickle
class P72(object):
    '''
    classdocs
    '''
    def __init__(self):
        '''
        Constructor
        '''
        F=open('prime100.txt','rb')
        self.p1=pickle.load(F)
        F.close()

        
    def Counting_fractions(self,d):
        cf=set(range(d))
        for n in self.p1:
            if n>d:break
            if gcd(d,n)==n:
                cf = cf-set(filter(lambda x:gcd(x,n)>1, cf))
        return len(cf)


    def calc(self,max_d):
        result = 0
        
        for d in range(2, max_d + 1):            
            result += self.Counting_fractions(d)
            if d%1000==0:print(str(d)+str(result))
        return result

# print(calc(1000000))
p=P72()
print(p.calc(1000000))
